#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*--- data definitions 数据结构定义 ---*/

struct Node {           /* a node in our linked list */
    char  *City;
    int    Temp;
    struct Node *Next;
};

typedef struct Node * Link; /* Links are pointers to nodes */

Link Head;              /* head of our linked list */
int  NodeCount;         /* how many nodes in the list */

/*--- functions declarations for linked lists 对链表定义的方法 ---*/

int  AddNodeAscend ( Link );        /* add a node           */
void CreateList ( void );           /* initialize list      */
int  DeleteNode ( Link );           /* delete a node        */
int  DuplicateNode ( Link, Link );  /* handle duplicate inserts 重复节点处理 */
void FreeNode ( Link );             /* free a node's memory */
void ShowNodes ( void );            /* show list of nodes   */
int  NodeCmp ( Link, Link );        /* compare two nodes    */

/*--- function definitions ---*/
/*将传入节点有序去重的加入链表*/
int AddNodeAscend ( Link to_add )
{
    Link   pn,   /* local copy of node to be added 定位需加入的节点*/
           prev, /* points to previous node 指向前节点 */
           curr; /* points to node being examined  指向检查节点 */
    struct Node dummy;
    int    i;

    /* Make a copy of the input node 复制到pn*/
    pn = ( Link ) malloc ( sizeof ( struct Node ));
    if ( pn == NULL )
        return 0;
    memcpy ( pn, to_add, sizeof ( struct Node ));

    /* set up a dummy node to simplify logic 设置辅助节点 */
    dummy.Next = Head;
    prev = &dummy;
    curr = Head;

    /* insert node pn 找到节点插入的位置*/
    for ( ;; prev = curr, curr = curr->Next )
    {
        if ( curr == NULL )
            break; /* reached the end */

        i = NodeCmp ( pn, curr );
        if ( i <= 0 )
             break; /* pn precedes curr */
    }
/*检查去重*/
    if ( curr && i == 0 ) /* we have a duplicate */
        if ( DuplicateNode ( curr, pn ) == 0 )
            return ( 1 ); /* bail out if DuplicateNode says to */

    prev->Next = pn;
    pn->Next = curr;

    Head = dummy.Next;
	NodeCount+=1;//yyw
    return ( 1 );
}

/*--------------------------------------------------------------
 * Handle the duplicate node. In this program,
 * we just delete the duplicate. 去重 直接释放参数节点
 *-------------------------------------------------------------*/
int DuplicateNode ( Link inlist, Link duplicate )
{
    FreeNode ( duplicate );
    return ( 0 );
}

/*从head往后逐个查找匹配进行删除*/
int DeleteNode ( Link to_delete )
{
    Link curr,  /* the current node */
         prev;  /* the previous node */
    int  i;

    /*--- Is there anything in the list? 链表空则不删---*/
    if ( Head == NULL )
        return ( 0 );

    /*--- If so, step through the list looking for the node 往后逐个查找需删节点---*/
    for ( prev = NULL, curr = Head;
        curr != NULL && ( i = NodeCmp ( to_delete, curr )) > 0;
        prev = curr, curr = curr->Next )
        /* loop around */ ;

    /*--- Found a match, so delete it 找到匹配的则删除 ---*/
    if ( curr != NULL && i == 0 )
    {
        if ( prev )
            prev->Next = curr->Next;
        else              /* deleting Head */
            Head = curr->Next;

        FreeNode ( curr );
        NodeCount -= 1;
        return ( 1 );
    }

    return ( 0 );
}

/*先比较节点的温度 温度相同再比较城市名 返回1 0 -1 */
int NodeCmp ( Link a, Link b )
{
    /* returns 1, 0, -1, depending on whether the data in
     * a is greater than, equal, or less than b.
     */

    /* if temps are unequal, return based on temp */
    if ( a->Temp != b->Temp )
        return ( a->Temp - b->Temp );

    /* else, return based on city's name */
    return strcmp ( a->City, b->City );
}

/* 初始化全局变量Head NodeCount 创建链表 */
void CreateList ( void )
{
    Head = NULL;
    NodeCount = 0;
}

/*释放节点的City和节点本身的空间*/
void FreeNode ( Link n )
{
    free ( n->City );
    free ( n );
}

/* 显示所有节点的城市温度信息，并且在中间节点后输出median */
void ShowNodes( void )
{
    Link pn;
    int count, median;

	///* compute the median node 计算中间节点 */
	median = NodeCount/2+1;//yyw

    /* step through the list printing cities and
     * temperatures. Announce the median temperature. 列出所有城市温度并声明中间值
     */
    if ( NodeCount ) /* only print if there's a node  只有当有节点时才打印*/
    {
        /* initialize the needed variables 初始化变量*/
        count = 0;     /* count of nodes we've printed count为已打印的节点数 */
        for ( pn = Head; pn; pn = pn->Next )
        {
            printf ( "%-20s: %3d", pn->City, pn->Temp );
            count += 1;
            /*在中间值后输出median*/
            if ( count == median )
                printf ( " --Median--" );
            printf ( "\n" );
        }
    }
    else
        printf ( "Empty list\n" );
}



/*--- main line ---*/
int main ( int argc, char *argv[] )
{
    FILE *fin;        /* file we'll be reading from 源文件 */
    char buffer[128]; /* where we'll read the file into 读入的缓冲区*/

    struct Node n;    /* the node we add each time 每次填入所实用的节点 */

 /* 判断参数个数是否符合要求 不符则返回相关提示信息 */
    if ( argc != 2 )
    {
        fprintf ( stderr, "Usage: citytemp filename.ext\n" );
        exit ( EXIT_FAILURE );
    }
 /* 获取源文件 */
    fin = fopen ( argv[1], "rt" );//第一个参数文件名
     /* 判断源文件能否打开 不符则返回相关提示信息 */
    if ( fin == NULL )
    {
        fprintf ( stderr, "Cannot open/find %s\n", argv[2] );
        exit ( EXIT_FAILURE );
    }

    /* Create and initialize the linked list to empty 创建并初始化链表*/
    CreateList();

    /*--- main loop  逐个将文件里数据升序加入到链表节点 ---*/
    while ( ! feof ( fin ))
    {
        /* read a record consisting of a line of text 读取由一行文本组成的记录放到buffer里 */
        if ( fgets ( buffer, 127, fin ) == NULL )
            break;

        /* get rid of the trailing carriage return 去掉最后的回车*/
        buffer [ strlen ( buffer ) - 1 ] = '\0';

        /* copy the city name to the node to be added 存入城市名*/
        n.City = strdup ( buffer + 3 );

        /* mark off the temperature and convert to int 将温度字符串转整型（atoi()）存入节点 */
        buffer[3] = '\0';
        n.Temp = atoi ( buffer );

        /* add the node to the list  将节点插入链表 */
        if ( AddNodeAscend ( &n ) == 0 )
        {
            fprintf ( stderr, "Error adding node. Aborting\n" );
            exit ( EXIT_FAILURE );
        }
    }

/* 输出展示链表*/
    ShowNodes();

    /* Now, delete something 删除头再展示 */
    printf( "\n" );
    DeleteNode ( Head );
    ShowNodes();

/*只要存在2个节点就删除第二个节点 并展示 只剩一个节点结束循环*/
    while (Head && Head->Next)
    {
        printf ( "\n" );
        DeleteNode ( Head->Next );
        ShowNodes();
    }
/*删除头展示链表*/
    printf ( "\n" );
    DeleteNode ( Head );
    ShowNodes();

    fclose ( fin );
    return ( EXIT_SUCCESS );
}